package com.kevin.Code.Backtrack;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Vinlee Xiao
 * @Classname GenerateParentheses1
 * @Description Leetcode 22. 括号生成  回溯算法 中等难度 二刷
 * @Date 2022/2/23 16:42
 * @Version 1.0
 */
public class GenerateParentheses1 {

    List<String> result = new ArrayList<>();

    /**
     * @param n 参数括号的大小
     * @return 返回左右括号组成的字符串集合
     */
    public List<String> generateParenthesis(int n) {

        char[] ch = new char[n * 2];
        backtrack(ch, n, n, 0);

        return result;
    }

    /**
     * 这一题关键的地方是如何让括号分布符合正常的括号顺序
     *
     * @param ch    字符数组
     * @param left  左边括号的数量
     * @param right 右边括号的数量
     * @param count 表示已经对第几个字符进行了赋值
     */
    private void backtrack(char[] ch, int left, int right, int count) {

        //将字符数组转换为字符串
        if (count == ch.length) {
            result.add(new String(ch));
            return;
        }

        //回溯中止的条件 组成的括号是否复合要求就是)( 这是right=2 left=3 不符合要求

        char[] parentheses = new char[]{'(', ')'};

        for (char c : parentheses) {
            if (right < left || right < 0 || left < 0) {
                continue;
            }
            if (c == '(' && left > 0) {
                ch[count] = '(';
                backtrack(ch, left - 1, right, count + 1);
                ch[count] = '.';
            } else if (c == ')' && right > 0) {
                ch[count] = ')';
                backtrack(ch, left, right - 1, count + 1);
                ch[count] = '.';
            }
        }
    }

    public static void main(String[] args) {
        GenerateParentheses1 generateParentheses1 = new GenerateParentheses1();
        List<String> list = generateParentheses1.generateParenthesis(3);
        for (String s : list) {
            System.out.println(s);
        }
    }
}
